// NC364 至少有 K 个重复字符的最长子串
// https://www.nowcoder.com/practice/5aabbcfc45e2443ab7b8c9988bca6616
//给定一个长度为 n 的字符串 s ，请你找出 s
//的最长子串，这个子串满足所有字符都出现大于等于 k 次。
//请你返回这个子串的长度。字符串中仅出现小写英文字母
//输入："aaabb",3
//返回值：3
//输入："aaabb",2
//返回值：5

#include <bits/stdc++.h>

using namespace std;

//#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

class Solution {
 public:
  // "cadabb",2
  int longestSubstring(string str_, int nMinK) {
    if (str_.length() < nMinK) {
      return 0;
    }
    size_t nMaxSubLen = 0;
    queue<string> quString;
    quString.push(str_);
    PF("push=%s\n", str_.c_str());
    while (!quString.empty()) {
      auto subtmp = quString.front();
      quString.pop();
      // aabbccdeeeee
      map<char, int> mapFreq;
      for (auto ch : subtmp) mapFreq[ch]++;
      for (auto [ch, num] : mapFreq) PF("map  ={%c,%d}\n", ch, num);
      int nStart = 0;
      int nEnd = 0;
      for (; nEnd < subtmp.length(); nEnd++) {
        // 字符数量不够,分割
        //    aaabbbcdddffff
        //          ^
        PF("=== %c, %d, min=%d\n", subtmp[nEnd], mapFreq[subtmp[nEnd]], nMinK);
        if (mapFreq[subtmp[nEnd]] < nMinK) {
          PF("freq=%c,%d\n", subtmp[nEnd], nEnd);
          int tmpLen = nEnd - nStart;
          if (tmpLen > 0 && tmpLen >= nMinK) {
            quString.push(subtmp.substr(nStart, tmpLen));
            PF("push=%s, [%d,%d\n", subtmp.substr(nStart, tmpLen).c_str(),
               nStart, nEnd);
          }
          nStart = nEnd + 1;  // next
          PF("next=%d,%d\n", nStart, nEnd);
        }
      }
      int tmpLen = nEnd - nStart;
      if (nStart > 0 && tmpLen > 0 && tmpLen >= nMinK) {
        quString.push(subtmp.substr(nStart, tmpLen));
        PF("push=%s,   %d,%d,%d\n", subtmp.substr(nStart, tmpLen).c_str(),
           tmpLen, nStart, nEnd);
      }
      if (nStart == 0) {
        nMaxSubLen = std::max(nMaxSubLen, subtmp.length());
      }
    }
    return nMaxSubLen;
  }
};

int main() {
  Solution sol;
  printf("%d\n", sol.longestSubstring("cadabb", 2));
  return 0;
}
